#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;
// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    bool isPalindrome(ListNode* head) {
        // 寻找中间位置(如果是奇数则为正中间，如果为偶数则为中间偏左侧)
        ListNode *node1 = head, *node2 = head;
        while (node2->next && node2->next->next) {
            node1 = node1->next;
            node2 = node2->next->next;
        }

        // 反转后半部分链表
        ListNode* node3 = reverseList(node1->next);

        // 比较前半部分和反转的后半部分是否相等
        node1 = head;
        while (node1 && node3) {
            if (node1->val != node3->val) {
                return false;
            }
            node1 = node1->next;
            node3 = node3->next;
        }
        return true;
    }

   private:
    ListNode* reverseList(ListNode* head) {
        // 反转链表
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
};

int main() {
    Solution solution;
    return 0;
}